﻿// 1003train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <vector>

using namespace std;

/*
 示例2
输入	
幸福de猪的个人专辑
幸福的猪的个人专辑
得 的
得 de

输出	
True
de 的
 */
class Union
{
public:
    unordered_map<string, string>parents;
    unordered_set<string>token_set;

    void addToken(string& token)
    {
        token_set.insert(token);
        if (parents.count(token) == 0)
        {
            parents[token] = token;
        }
    }

    string findParent(string& token)
    {
        if (parents.count(token) == 0)
            return "";
        string token_p = token;
        while (parents.at(token_p) != token_p)
        {
            token_p = parents.at(token);
        }
        return token_p;
    }

    void unionToken(string& token_x, string& token_y)
    {
        if (findParent(token_x) != findParent(token_y))
        {
            parents[findParent(token_y)] = findParent(token_x);
        }
    }
    //Union
};

class Solution01
{
public:
    struct Node
    {
        bool res = false;
        vector<pair<string, string>>token_v;

        void addPair(pair<string, string>& str_p)
        {
            token_v.push_back(str_p);
        }

        Node() = default;
        Node(bool res) :res(res) {};
        //Node
    };

    Node* findSimilar(string&str_x, string&str_y)
    {
        pair<string, string>curr_p = make_pair(str_x, str_y);
        if (token_map.count(curr_p) > 0)
        {
            return token_map.at(curr_p);
        }

        if (str_x.empty() && str_y.empty())
        {
            return new Node(true);
        }

        //查看相同的直接跳过
        if (!str_x.empty() && !str_y.empty() && str_x[0] == str_y[0])
        {
            //直接继承子串的结果
            string sub_x = str_x.substr(1);
            string sub_y = str_y.substr(1);

            Node* node = findSimilar(sub_x, sub_y);
            if (node->res)
            {
                pair<string, string>token_p = make_pair(sub_x, sub_y);
                token_map[token_p] = node;
                return node;
            }
        }

        //查看相似
        string similar_x, similar_y;
        for (auto& similar : union_.token_set)
        {
            if (str_x.rfind(similar, 0) == 0)
            {
                similar_x = similar;
            }
            if (str_y.rfind(similar, 0) == 0)
            {
                similar_y = similar;
            }
        }

        if (similar_x.empty()|| similar_y.empty())
            return new Node(false);

        if (union_.findParent(similar_x) == union_.findParent(similar_y))
        {
            string sub_x = str_x.substr(similar_x.size());
            string sub_y = str_y.substr(similar_y.size());

            Node* res_node = findSimilar(sub_x, sub_y);
            //保证字典序
            if (!res_node->res)
            {
                return new Node(false);
            }

            //如果子串返回结果无异议
            //把当前相似加进去
            pair<string, string>str_p = make_pair(similar_x, similar_y);
            res_node->addPair(str_p);
            pair<string, string>key = make_pair(str_x, str_y);
            token_map[key] = res_node;
            return res_node;
            //find
        }

        return new Node(false);
	    //similar
    }

    string handleStr(string&str)
    {
        if (str.find('(') == string::npos)
            return str;

        bool is_left = false;
        string new_str;
        for (auto&ch:str)
        {
            if (ch == '(')
            {
                is_left = true;
                continue;
            }
            if (ch == ')')
            {
                is_left = false;
                continue;
            }
            if (is_left) continue;
            new_str += ch;
        }
        return new_str;
        //
    }

    Solution01(string&str_x, string&str_y,vector<vector<string>>&token_vec)
    {
        bool parenthesis = false;
        for (auto&item_v:token_vec)
        {
            if (item_v[0]=="(***)")
            {
                parenthesis = true;
                continue;
            }

            for (auto&token:item_v)
            {
                union_.addToken(token);
            }
            int item_size = item_v.size();
            for (int i=1; i<item_size; i++)
            {
                union_.unionToken(item_v[0], item_v[1]);
            }
        }

        if (parenthesis)
        {
            str_x = handleStr(str_x);
            str_y = handleStr(str_y);
        }

        Node* result = findSimilar(str_x, str_y);

        if (result->res)
        {
            cout << "True" << '\n';
            if (parenthesis)
            {
                cout << "(***)" << '\n';
            }
            for (auto&item:result->token_v)
            {
                cout << item.first << ' ' <<item.second << '\n';
            }
            return;
        }
        
        cout << "False" << '\n';
        int min_size = min(str_x.size(), str_y.size());
        int diff_pos = 0;
        for (int i=0; i<min_size;i++)
        {
            if (str_x[i] != str_y[i])
            {
                diff_pos = i;
                break;
            }
        }
        cout << str_x.substr(diff_pos) << ' ' << str_y.substr(diff_pos);
	    //Solution01
    }
private:
    Union union_;
    map<pair<string, string>, Node*>token_map;
};

int main()
{
    string str_x, str_y;
    getline(cin, str_x);
    getline(cin, str_y);

    vector<vector<string>>token_v;

    string input;
    while (getline(cin,input))
    {
        if (input.empty()) break;
        vector<string>item_v;
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            item_v.push_back(token);
        }
        token_v.push_back(item_v);
    }
    Solution01 solu(str_x, str_y, token_v);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
